package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * tree
 * 971. 翻转二叉树以匹配先序遍历
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/29 17:40
 */
public class FlipMatchVoyage {


    public static void main(String[] args) {
        FlipMatchVoyage test = new FlipMatchVoyage();
        TreeNode instance = TreeNode.getInstance3();
        int[] arr = {5, -2};
        List<Integer> list = test.flipMatchVoyage(instance, arr);
        System.out.println(list);
    }

    private int n = 0;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        List<Integer> list = new ArrayList<>();
        boolean b = find(root, voyage, list);
        if (b) {
            return list;
        }
        list = new ArrayList<>();
        list.add(-1);
        return list;
    }

    private boolean find(TreeNode root, int[] voyage, List<Integer> list) {
        if (root == null) {
            return true;
        }
        if (n == voyage.length || root.val != voyage[n]) {
            return false;
        }
        n++;
        if (find(root.left, voyage, list) && find(root.right, voyage, list)) {
            return true;
        }
        list.add(root.val);
        if (find(root.right, voyage, list) && find(root.left, voyage, list)) {
            return true;
        }
        n--;
        list.remove(list.size() - 1);
        return false;
    }

}
